package everyday.m20230309;

/**
 * 剑指offer47题
 */
public class Q20230308 {

    /**
     * 思路：设置dp[i][j] 表示最后一格是grid[i][j]最大的
     * 那么，dp[i+1][j+1] 等于max(dp[i][j+1],dp[i+1][j]) + grip[i+1][j+1]
     *
     * @param grid
     * @return
     */
    public int maxValue(int[][] grid) {
        // 先向右走再向下走
        int[][] dp = new int[grid.length + 1][grid[0].length + 1];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                dp[i + 1][j + 1] = Integer.max(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
            }
        }
        return dp[grid.length][grid[0].length];
    }

    public static void main(String[] args) {
        Q20230308 q20230308 = new Q20230308();
        System.out.println(q20230308.maxValue(new int[][]{
                new int[] {1,3,1},
                new int[] {1, 5, 1},
                new int[] {4,2,1}
        }));
    }
}
